Q: In what time can a 2-d tree be constructed?
Solution: A perfectly balanced 2-d tree can be constructed in O(N log N) time. This value is computed mathematically.
Q: In a two-dimensional search tree, the root is arbitrarily chosen to be?
Solution: In a two- dimensional k-d tree (i.e.) 2-d tree, the root is arbitrarily chosen to be an odd level and it applies to all 2-d trees.
Q: Which of the following is the simplest data structure that supports range searching?
Solution: K-d trees are the simplest data structure that supports range searching and also it achieves the respectable running time.
Q: In a k-d tree, k originally meant?
Solution: Initially, 2-d trees were created. Then, 3-d trees, 4-trees etc., where k meant the number of dimensions.
Q: What will be the correct sequence of insertion for the following k-d tree?
Solution: The correct sequence of insertion of the above given tree is (30,40),(5,25),(10,12),(70,70),(50,30),(35,45). The insertion is given by, first left, then right.
Q: Each level in a k-d tree is made of?
Solution: Each level in a k-d tree is made of dimensions and cutting. Cutting and dimensions are used for insertion, deletion and searching purposes.
Q: What is the worst case of finding the nearest neighbour?
Solution: The worst case analysis of finding the nearest neighbour in a k-d tree is mathematically found to be O(N).
Q: What is the run time of finding the nearest neighbour in a k-d tree?
Solution: The run time of finding the nearest neighbour in a kd tree is given as O(2d log N) where 2d is the time taken to search the neighbourhood.
Q: Several kinds of queries are possible on a k-d called as?
Solution: Several range queries are possible on a k-d tree. One of the range queries is known as a partial match query.
Q: Who invented k-d trees?
Solution: Jon Bentley found k-d trees. Rudolf Bayer found red black trees. Arne Andersson found AA- trees.
| You Have Score | /10 |